"""
Problem 58: https://projecteuler.net/problem=58

Starting with 1 and spiralling anticlockwise in the following way,
a square spiral with side length 7 is formed.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

It is interesting to note that the odd squares lie along the bottom right
diagonal ,but what is more interesting is that 8 out of the 13 numbers
lying along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.

If one complete new layer is wrapped around the spiral above,
a square spiral with side length 9 will be formed.
If this process is continued,
what is the side length of the square spiral for which
the ratio of primes along both diagonals first falls below 10%?
"""

# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = VSCODE Python3.8.3
@creat_time = 2022/5/18
'''


def isprime(n: int) -> bool:
    if n < 2:
        return False

    if n == 2:
        return True
    
    if n%2==0:
        return False

    n_sqrt = n**0.5
    if n_sqrt == int(n_sqrt):
        return False

    for i in range(3, int(n_sqrt),2):
        if n % i == 0:
            return False

    return True


def solution(percentlimit: float = 1/10) -> int:
    '''
    circle 0     1      2       3  ... c
    ---------------------------------------------------------- 
           1     3     13       31 ... 4c^2 - 2c + 1
           1     5     17       37     4c^2 + 1  
           1     7     21       43     4c^2 + 2c + 1
           1     9     25       49     4c^2 + 4c + 1 = (2c+1)^2

    total of diagonal nums is 4c - 3
    '''

    c = 1
    percent = (3,5)

    while percent[0]/percent[1] >= percentlimit:
        c += 1
        totals = percent[1] + 4
        primsNum = percent[0] + sum([
                                    isprime(4*(c*c) - 2*c + 1),
                                    isprime(4*(c*c) + 1),
                                    isprime(4*(c*c) + 2*c + 1)
                                    ])
        percent = (primsNum, totals)
        print(c, percent[0]/percent[1])

    return c, percent[0]/percent[1]


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)

    print(solution())
    # (13120, 0.09999809454850327)
